/**
 * 
 */
package greedy;

import java.util.Arrays;

/**
 * @author michael
 *
 */
public class Candy {

	/**
	There are N children standing in a line. Each child is assigned a rating value.
	
	You are giving candies to these children subjected to the following requirements:
	
	Each child must have at least one candy.
	Children with a higher rating get more candies than their neighbors.
	What is the minimum candies you must give?
	 */
	// space and time O(n)
    public int candy(int[] ratings) {
    	
    	int size = ratings.length;
    	int[] numbers = new int[size];
    	Arrays.fill(numbers, 1);
    	int result = 0;
    	
    	for (int i = 1; i < size; i++) {
    		if (ratings[i] > ratings[i - 1]) {
    			numbers[i] = numbers[i - 1] + 1;
    		}
    	}
    	
    	for (int i = size - 1; i >= 1; i--) {
    		if (ratings[i - 1] > ratings[i]) {
    			numbers[i - 1] = Math.max(numbers[i-1], numbers[i] + 1);
    		}
    	}
        for (int i = 0; i < size; i++) {
        	result += numbers[i];
        }
        
        return result;
    }
	
	/**
	 * 
	 */
	public Candy() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
